module cl {
	export class RoutePay {
		public constructor(public pay : number, public route : number[]){}
	}
	export class PayMap {
		public constructor(public payMap : number[], public rootMap : number[]){}
	}

	export class RouteNode {
		public constructor(public pay : number, public previous : number, public next : number, public root : number, public waited : boolean){}
	}

	export class RouteEngine {
		public constructor(private _neighborMap : number[][]) {}

		private _node : RouteNode[];

		private _createNodeArray(tileCount : number) : void {
			this._node = new Array(tileCount);
			for (let idx = 0; idx < tileCount; idx++){
				this._node[idx] = new RouteNode(32767, idx-1, idx+1, -1, true);
			}
			this._node[0].previous = -1;
			this._node[tileCount-1].next = -1;
		}

		private _moveStartToHead(startIndex : number) : void {
			if (startIndex != 0){
				this._node[this._node[startIndex].previous].next = this._node[startIndex].next;
				if (this._node[startIndex].next != -1)
					this._node[this._node[startIndex].next].previous = this._node[startIndex].previous;

				this._node[startIndex].previous = this._node[0].previous;
				this._node[startIndex].next = 0;
				this._node[0].previous = startIndex;
			}
		}

		private _movePlace(tid : number, preTid : number) : void {
			if (preTid != -1){
				if (this._node[tid].previous != -1)
					this._node[this._node[tid].previous].next = this._node[tid].next;
				if (this._node[tid].next != -1)
					this._node[this._node[tid].next].previous = this._node[tid].previous;

				this._node[tid].previous = preTid;
				this._node[tid].next = this._node[preTid].next;

				this._node[this._node[preTid].next].previous = tid;
				this._node[preTid].next = tid;
			}
		}

		/** 找到最后一个 pay > pay[tid] 的前一个 */
		private _findValidNode(tid : number) : number {
			let currentTid = this._node[tid].previous;
			if (this._node[currentTid].pay <= this._node[tid].pay)
				return -1; // 已排序
			while (this._node[currentTid].pay > this._node[tid].pay){
				currentTid = this._node[currentTid].previous;
			}
			return currentTid;
		}

		public routePay(costmap : number[], startTid : number, endTid : number, isGenRoute : boolean) : RoutePay {
			if (costmap[startTid] == -1 || costmap[endTid] == -1){
				return new RoutePay(-1, []);
			}

			this._createNodeArray(costmap.length);
			this._moveStartToHead(startTid);
			this._node[startTid].pay = 0;
			let currentTid = startTid;
			while (currentTid != -1 && currentTid != endTid){
				if (this._node[currentTid].pay >= 32767) {
					currentTid = -1;
					continue;
				}

				this._node[currentTid].waited = false;

				let neighbors = this._neighborMap[currentTid];

				for (let neighborTid of neighbors){
					if (this._node[neighborTid].waited && costmap[neighborTid] >= 0){
						let pay = this._node[currentTid].pay + costmap[currentTid] + costmap[neighborTid];
						if (pay < this._node[neighborTid].pay){
							this._node[neighborTid].pay = pay;
							this._node[neighborTid].root = currentTid;
							this._movePlace(neighborTid, this._findValidNode(neighborTid));
						}
					}
				}

				currentTid = this._node[currentTid].next;
			}
			if (currentTid == -1){
				return new RoutePay(-1, []);
			} else{
				let pay = this._node[currentTid].pay;
				let route : number[] = [];
				if (isGenRoute){
					for (let tid = 0; currentTid != startTid; currentTid = this._node[currentTid].root, tid++){
						route[tid] = currentTid;
					}
					route.push(startTid);
				}
				return new RoutePay(pay, route);
			}
		}

		public payMap(costmap, startTid, maxpay) : PayMap {
			let routePayMap : number[] = [];
			let routeRootMap : number[] = [];
			for (let i = 0; i < costmap.length; i++){
				routePayMap.push(-1);
				routeRootMap.push(-1);
			}
			if (costmap[startTid] < 0){
				return new PayMap(routePayMap, routeRootMap);
			}

			this._createNodeArray(costmap.length);
			this._moveStartToHead(startTid);
			this._node[startTid].pay = 0;
			let currentTid = startTid;
			while (currentTid != -1 && this._node[currentTid].pay <= maxpay){
				if (this._node[currentTid].pay >= 32767) {
					currentTid = -1;
					continue;
				}

				this._node[currentTid].waited = false;

				let neighbors = this._neighborMap[currentTid];

				for (let neighborTid of neighbors){
					if (this._node[neighborTid].waited && costmap[neighborTid] >= 0){
						let pay = this._node[currentTid].pay + costmap[currentTid] + costmap[neighborTid];
						if (pay < this._node[neighborTid].pay){
							this._node[neighborTid].pay = pay;
							this._node[neighborTid].root = currentTid;
							this._movePlace(neighborTid, this._findValidNode(neighborTid));
						}
					}
				}

				currentTid = this._node[currentTid].next;
			}
			for (let tmpid = 0; tmpid < this._node.length; tmpid++){
				if (this._node[tmpid].pay <= maxpay){
					routePayMap[tmpid] = this._node[tmpid].pay;
					routeRootMap[tmpid] = this._node[tmpid].root;
				} else {
					routePayMap[tmpid] = -1;
					routeRootMap[tmpid] = -1;
				}
			}
			return new PayMap(routePayMap, routeRootMap);
		}
	}
}